package Simple;
/**
 * Findout if the linkedlist has a cycle.
 * @author YC
 *
 */
public class ListLoopQuestion {

	public static class ListNode{
		public int value;
		public ListNode next;
	
	}

	
	public static boolean hasLoops(ListNode myList){
		
		ListNode slow = myList;   //pointer1 with slower speed
		ListNode fast = myList;	//pointer2 with faster speed
        boolean isCycle = false;   // a boolean varible to return
		//check if here is a cycle
        while(slow!=null && fast!= null){
			//if p1 doesn't have next, means we reach the end of list and
        	//here are no cycles
        	if(slow.next == null){ 
				break;
        	}
			else{
				slow=slow.next;   //p1 go forward one step				
			}
				      	
        	//if p2 doesn't have next, or the next of p2's next is empty
        	//it means we reach the end of list and here are no cycles
			if(fast.next == null || fast.next.next == null){ 
				break;
			}
			else{
				fast=fast.next.next;  //p2 step forward twice
			}

			
			//Because the value is distinct integers, so onces p1 and p2 has the
			//same value, they must point to the same node 
			if(slow.value==fast.value) {
				isCycle = true;   //change value of return varible to true
			    break;    //break the while loop in case of infinite loop
			}
		}
		return isCycle;	
	}
	
	public static void main(String[] args) {
		// TODO Auto-generated method stub

		ListNode l1 = new ListNode() ;
		ListNode l2 = new ListNode() ;	
		ListNode l3 = new ListNode() ;
		ListNode l4 = new ListNode() ;
		ListNode l5 = new ListNode() ;
		l1.value = 1;
		l2.value = 2;
		l3.value = 3;
		l4.value = 4;
		l5.value = 5;
		l1.next = l2;
		l2.next = l3;
		l3.next = l4;
		l4.next = l5;
		l5.next = null;
//		l5.next.next = null;
		boolean loop = hasLoops(l1);
		System.out.println(loop);
	}

}
